use std::rc::Rc;
use std::cell::RefCell;
use std::collections::BinaryHeap;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

struct Solution;

impl Solution {
    /// 采用堆解决最容易了 只有40 说明不是最好的
    /// 采用中序
    pub fn kth_smallest_self(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
        let mut heap = BinaryHeap::new();
        Solution::add_heap(root, &mut heap);
        let len = heap.len();
        let k = len - (k as usize);
        for _ in 0..k {
            heap.pop();
        }
        heap.pop().unwrap()
    }

    fn add_heap(root: Option<Rc<RefCell<TreeNode>>>, heap: &mut BinaryHeap<i32>) {
        if let Some(root_rc) = root {
            heap.push(root_rc.borrow().val);
            Solution::add_heap(root_rc.borrow().left.clone(), heap);
            Solution::add_heap(root_rc.borrow().right.clone(), heap);
        }
    }

    pub fn kth_smallest(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
        let mut k = k;
        Solution::inorder(&root, &mut k).unwrap()
    }

    fn inorder(root: &Option<Rc<RefCell<TreeNode>>>, k: &mut i32) -> Option<i32> {
        if let Some(root_rc) = root {
            let left = Solution::inorder(&root_rc.borrow().left, k);
            if left.is_some() {
                return left;
            }

            if *k == 1 {
                return Some(root_rc.borrow().val);
            }
            *k -= 1;

            let right = Solution::inorder(&root_rc.borrow().right, k);
            if right.is_some() {
                return right;
            }
        }
        None
    }
}


fn main() {
    Solution::kth_smallest_self(None, 0);
    Solution::kth_smallest(None, 0);
}

